package zuochengyun.chapter8;

//数组的partition调整
//涉及到对数组在给定要求的情况下实现O(n)的排序
public class Partition {

	public static void main(String[] args) {
		Partition object = new Partition();
		int[] arr = {0, 2, 1, 0, 2, 1, 2, 1,2 , 1,2, 1,0 ,2, 1, 1, 2, 0, 2, 1, 2, 1, 0};
		object.sort(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		int[] nums = {5, 4, 9, 7, 6, 3, 4, 2, 6, 9, 3, 1};
		object.sort(nums, 5);
		for (int i = 0; i < nums.length; i++) {
			System.out.print(nums[i] + " ");
		}
		System.out.println();
	}
	
	
	//给定一个有序数组，使得左半部分没有重复元素且升序，不用保证右半部分是否有序
	public void leftUnique(int[] arr){
		if(arr == null || arr.length < 2){
			return;
		}
		//u表示arr[0...u]都是无重复元素且升序的
		int u = 0;
		int i = 1;
		while(i < arr.length){
			if(arr[i] != arr[u]){
				swap(arr, ++u, i++);
			}
		}
	}
	
	public void swap(int[] arr, int i, int j){
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	
	//变形：数组中只可能有0， 1， 2，将0全部放在左边，1放在中间，2放在右边
	public void sort(int[] arr){
		if(arr == null || arr.length < 2){
			return;
		}
		//left表示的是0的右边界arr[0...left]都是0，初始为-1;
		int left = -1;
		//left表示的是2的左边界arr[right...n - 1]都是2，初始为n;
		int right = arr.length;
		//index表示的是1的左边界，arr[left + 1...index]是1
		int index = 0;
		while(index < right){
			if(arr[index] == 0){
				swap(arr, ++left, index++);
			}else if(arr[index] == 1){
				index++;
			}else{
				//等于2的时候我们将--right与index交换，因为此时我们不知道交换来的是几，所以index不变
				swap(arr, --right, index);
			}
		}
	}
	
	
	//再变形，将数组中所有小于k的数放置左边，等于k的数放置中间，大于k的数放置右边
	public void sort(int[] arr, int k){
		if(arr == null || arr.length < 2){
			return;
		}
		//left表示的是0的右边界arr[0...left]都是0，初始为-1;
		int left = -1;
		//left表示的是2的左边界arr[right...n - 1]都是2，初始为n;
		int right = arr.length;
		//index表示的是1的左边界，arr[left + 1...index]是1
		int index = 0;
		while(index < right){
			if(arr[index] < k){
				swap(arr, ++left, index++);
			}else if(arr[index] == k){
				index++;
			}else{
				//等于2的时候我们将--right与index交换，因为此时我们不知道交换来的是几，所以index不变
				swap(arr, --right, index);
			}
		}
	}
}
